#include <iostream>
#include <time.h>

const int capacity = 10;

class MaxHeap
{
public:
    MaxHeap() : size(0) {}
    void Insert(int value)
    {
        array[size] = value;
        Siftup(size);
        size++;
    }

    void RemoveRoot()
    {
        if (size == 0)
            return;
        array[0] = array[--size];
        Siftdown(0); // 把根下沉
    }

    int &GetRoot()
    {
        return array[0];
    }

    void show()
    {
        for (int i = 0; i < size; i++)
        {
            std::cout << array[i] << " ";
        }
        std::cout << std::endl;
    }

private:
    int GetParents(int i) { return (i - 1) / 2; }
    int GetLeftChild(int i) { return 2 * i + 1; }
    int GetRightChild(int i) { return 2 * i + 2; }

    void Siftup(int i) // 上浮操作
    {
        while (i > 0 && array[i] > array[GetParents(i)])
        {
            std::swap(array[i], array[GetParents(i)]);
            i = GetParents(i);
        }
    }

    void Siftdown(int i) // 下沉操作
    {
        int leftChild = GetLeftChild(i);
        int rightChild = GetRightChild(i);

        int Max = i;
        // 左孩子存在且值比自身大
        if (leftChild < size && array[leftChild] > array[i])
        {
            Max = leftChild;
        }

        // 右孩子存在且值比自身和左孩子更大
        if (rightChild < size && array[rightChild] > array[Max])
        {
            Max = rightChild;
        }

        if (Max != i)
        {
            std::swap(array[i], array[Max]);
            Siftdown(Max);
        }
    }

    int array[capacity];
    int size; // 当前数组元素个数
};

int main()
{
    srand(time(nullptr));
    int a[20];
    for (int i = 0; i < 20; i++)
    {
        a[i] = rand() % 20 + 1;
    }
    for(int i=0; i<20; i++)
    {
        std::cout<<a[i]<<" ";
    }
    std::cout<<std::endl;
    MaxHeap h;
    for(int i=0; i<20; i++)
    {
        if(i<5)
        {
            h.Insert(a[i]);
        }
        else
        {
            if(a[i]<h.GetRoot())
            {
                h.RemoveRoot();
                h.Insert(a[i]);
            }
        }
    }
    h.show();
    return 0;
}